//
// Created by zhulingfeng on 2020/3/6.
//

#include "binary_search.hpp"
int BinarySearch(const std::vector<int>& vector, int target) {
  int lo = 0, hi = (int)vector.size() - 1;
  while (lo <= hi) {
    int mid = lo + (hi - lo) / 2;
    if (vector[mid] > target)
      hi = mid - 1;
    else if (vector[mid] < target)
      lo = mid + 1;
    else
      return mid;
  }
  return -1;
}
int BinarySearch(const std::vector<int>& vector, int target, int lo, int hi) {
  while (lo <= hi) {
    int mid = lo + (hi - lo) / 2;
    if (vector[mid] > target)
      hi = mid - 1;
    else if (vector[mid] < target)
      lo = mid + 1;
    else
      return mid;
  }
  return -1;
}

std::vector<int> SearchRange(const std::vector<int>& array, int target) {
  std::vector<int> res = {-1, -1};
  if (array.empty()) return res;
  /** Binary search **/
  int lo = 0, hi = (int)array.size() - 1, mid = 0;
  while (lo <= hi) {
    mid = lo + (hi - lo) / 2;
    if (array[mid] > target)
      hi = mid - 1;
    else if (array[mid] < target)
      lo = mid + 1;
    else
      break;
  }
  // Return if can't find target.
  if (array[mid] != target) return res;
  /** Search first and last position with value equal to target**/
  // Note the already changed variable lo and hi are
  // still effective, no need to reinitialize.
  int first_position = mid, last_position = mid;
  // Search first position.
  int hi_first = mid - 1;
  while (lo <= hi_first) {
    mid = lo + (hi_first - lo) / 2;
    if (array[mid] == target) {
      first_position = mid;
      hi_first = mid - 1;
    } else
      lo = mid + 1;
  }
  // Search last position.
  int lo_last = mid + 1;
  while (lo_last <= hi) {
    mid = lo_last + (hi - lo_last) / 2;
    if (array[mid] == target) {
      last_position = mid;
      lo_last = mid + 1;
    } else
      hi = mid - 1;
  }
  res[0] = first_position;
  res[1] = last_position;
  return res;
}

std::vector<int> SearchRangeWithTricks(const std::vector<int>& array,
                                       int target) {
  std::vector<int> res = {-1, -1};
  if (array.empty()) return res;
  /** Binary search **/
  int lo = 0, hi = (int)array.size() - 1, mid = 0;
  while (lo <= hi) {
    mid = lo + (hi - lo) / 2;
    if (array[mid] > target)
      hi = mid - 1;
    else if (array[mid] < target)
      lo = mid + 1;
    else
      break;
  }
  // Return if can't find target.
  if (array[mid] != target) return res;
  /** Search first and last position with value equal to target**/
  // Note the already changed variable lo and hi are
  // still effective, no need to reinitialize.
  int first = mid, last = mid;
  // Search first position.
  while (lo < first) {  // Notice it's <, not <=, to avoid endless loop when
    // first=lo=mid
    mid = lo + (first - lo) / 2;
    if (array[mid] == target)
      first = mid;  // Notice it not narrow right search range.
    else
      lo = mid + 1;  // Only increase left search range
  }
  // Search last position.
  while (last < hi) {
    // +1 to avoid endless loop when hi=last+1 and mid=last.
    mid = last + (hi - last + 1) / 2;
    if (array[mid] == target)
      last = mid;  // Notice it not narrow left search range.
    else
      hi = mid - 1;  // decrease right search range
  }
  res[0] = first;
  res[1] = last;
  return res;
}
int SearchRotatedArrayWithoutDuplicates(std::vector<int>& array, int target) {
  int lo = 0, hi = (int)array.size() - 1;
  int mid;
  while (lo <= hi) {
    mid = lo + (hi - lo) / 2;
    if (array[mid] == target) return mid;
    // < and = can be handel together.
    if (array[lo] <= array[mid]) {
      if (array[lo] <= target && target <= array[mid])
        hi = mid;
      else
        lo = mid + 1;
    } else {
      if (array[mid] <= target && target <= array[hi])
        lo = mid;
      else
        hi = mid - 1;
    }
  }
  return -1;
}
int SearchRotatedArrayWithoutDuplicates2(const std::vector<int>& array,
                                         int target) {
  if (array.empty()) return -1;
  if (target == array[0]) return 0;
  if (array[0] <= array[array.size() - 1])
    return BinarySearch(array, target, 0, (int)array.size() - 1);
  int size = array.size();
  int v = array[0];
  int lo = 1, hi = size - 1, mid = 0;
  // Search min value.
  while (lo <= hi) {
    mid = lo + (hi - lo) / 2;
    if (array[mid] > v)
      lo = mid + 1;
    else
      hi = mid - 1;
  }
  // Binary search target.
  if (target > v)
    return BinarySearch(array, target, 1, mid - 1);
  else
    return BinarySearch(array, target, mid, size - 1);
}
int SearchRotatedArray(std::vector<int>& array, int target) {
  int lo = 0, hi = (int)array.size() - 1;
  int mid;
  while (lo <= hi) {
    mid = lo + (hi - lo) / 2;
    if (array[mid] == target) return mid;
    if (array[lo] == array[mid]) {
      // Solution 1: Move mid
      // int i = mid + 1;
      // while (i <= hi) {
      //   if (array[i] == array[lo])
      //     i++;
      //   else
      //     break;
      // }
      // if (i > hi)
      //   hi = mid - 1;
      // else
      //   lo = i;
      // Solution 2: Move lo
      lo++;
    } else if (array[lo] < array[mid]) {
      if (array[lo] <= target && target <= array[mid])
        hi = mid;
      else
        lo = mid + 1;
    } else {
      if (array[mid] <= target && target <= array[hi])
        lo = mid;
      else
        hi = mid - 1;
    }
  }
  return -1;
}
